
//branch and bound

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>  // we are using assert.h to check some conditions remain true
#include <math.h>

#define DOUB_MAX 10e30  // a large number, must be greater than max value of any solution
#define SIZE 100000 // an estimate of how large the priority queue could become
#define NITEMS 1000 // an overstimate of the number of items

int C;     // capacity of the knapsack (total weight that can be stored)
FILE *fp;
int N;     // total number of items available
int *w;  // knapsack item weights vector
int *v;  // knapsack item profits vector
int *kindex;  // a list of item indexes (we can sort these instead of moving the items)
int current_best=0;
int M=0; // the number of items currently stored in the priority queue
int QUIET=0; // can be set to 1 to suppress output

// the structure for a solution. All of this will be stored in the priority queue
typedef struct sol
{
  int string[NITEMS+1];  // binary solution vector
  int val;               // its value
  int fixed;             // the number of items that are fixed to either 0 or 1, not *
  double bound;          // the upper bound value of the solution
}p;

p *a;  // the knapsack solutions. To be stored in a priority queue

// function prototypes
void sol_details(p *sol);
extern void read_knapsack_instance(char *filename);
extern void sort_by_ratio();
extern int print_sol2(int *s,  int *tv, int *tw);
void branch_and_bound(int *x);
void copy_string(int *from, int *to);

void upheap(int k)
{
  p v;
  v=a[k]; a[0].bound=DOUB_MAX;
  
  while (a[k/2].bound<=v.bound)
    {
      a[k]=a[k/2]; k=k/2;
    }
  a[k]=v;
}

void insert(p el)
{
  assert(M<SIZE-1);
  a[++M]=el;
  upheap(M);
}

void downheap(int k)
{
  int j;
  p v;
  v = a[k];
  while(k<= M/2)
    {
      j=k+k;
      if(j<M && a[j].bound<a[j+1].bound)
	j++;
      if(v.bound>=a[j].bound)
	break;
      a[k]=a[j]; k=j;
    }
  a[k]=v;
}

p _remove()
{
  p v=a[1];
  a[1]=a[M--];
  downheap(1);
  return v;
}


void print_sol(p *sol)
{
  int i;
  printf("%d %g ", sol->val, sol->bound);
  for(i=1;i<=sol->fixed;i++)
    printf("%d", sol->string[i]);
  while(i<=N)
    {
      printf("*");
      i++;
    }
  printf("\n");
}

void frac_bound(p *x, int fix)
{
  // Updates the values x->val and x->bound
  
  // Computes the fractional knapsack upper bound
  // given a binary vector of items, where the first
  // "fix" of them are fixed. All that must be done
  // is compute the value of the fixed part; this is the
  // value which goes in x->val
  // then
  // add to that the value obtained by adding in
  // items beyond the fixed part until the capacity
  // is exceeded. For the exceeded capacity, the fraction
  // of the last item added which would just fill the knapsack
  // is taken. This fraction of profit/value is added to the
  // total. This is the required upper bound.

  // Everything above assumes items are sorted in decreasing
  // profit/weight ratio
  

  /* YOUR CODE GOES HERE */
  

}


int main(int argc, char *argv[1])
{
  int *x;    // binary vector indicating items to pack
  int tv, tw;  // total value and total weight of items packed

  read_knapsack_instance(argv[1]);

  assert(NITEMS>=N);
 
  if((x = (int *)malloc((N+1)*sizeof(int)))==NULL)
    {      
      fprintf(stderr,"Problem allocating x vector\n");
      exit(1);
    }

  sort_by_ratio();

  if((a = (p *)malloc(sizeof(p)*SIZE))==NULL)
    {      
      fprintf(stderr,"Problem allocating memory for priority queue. Reduce SIZE.\n");
      exit(1);
    }

  branch_and_bound(x);
  printf("Branch and Bound Solution of Knapsack is:\n");
  print_sol2(x,&tv,&tw);
  return(0);
}


void branch_and_bound(int *x)
{
  // branch and bound

  // Output:  the solution vector of the optimal solution should be put in x

  //  start with the empty string
  // compute its value and its bound
  // put current_best = to its value
  // store it in the priority queue
  
  // LOOP until upper bound is not greater than current_best:
  // remove the first item in the queue
  // construct two children, 1 with a 1 added, 1 with a O added
  // FOREACH CHILD:
  // compute the value and bound
  // if value is greater than current_best, set current_best to it
  // add the children to the queue

  p par; // the parent solution
  p c1, c2; // the two children

  // this function should call
  // frac_bound() to compute value and bound of solutions
  // and print_sol() to print results as it goes

  // YOUR BRANCH AND BOUND CODE GOES HERE

}
  

void copy_string(int *from, int *to)
{
  int i;
  for(i=0;i<N;i++)
    {
      to[i]=from[i];
    }
}
